package simpledb.optimizer;

import simpledb.execution.Predicate;

/** A class to represent a fixed-width histogram over a single integer-based field.
 */
public class IntHistogram {
    private int[] counts;
    private final int min;
    private final int max;
    private final int width;
    private int ntup;
    /**
     * Create a new IntHistogram.
     * 
     * This IntHistogram should maintain a histogram of integer values that it receives.
     * It should split the histogram into "buckets" buckets.
     * 
     * The values that are being histogrammed will be provided one-at-a-time through the "addValue()" function.
     * 
     * Your implementation should use space and have execution time that are both
     * constant with respect to the number of values being histogrammed.  For example, you shouldn't 
     * simply store every value that you see in a sorted list.
     * 
     * @param buckets The number of buckets to split the input value into.
     * @param min The minimum integer value that will ever be passed to this class for histogramming
     * @param max The maximum integer value that will ever be passed to this class for histogramming
     */
    public IntHistogram(int buckets, int min, int max) {
    	// some code goes here
        counts = new int[buckets];
        this.min=min;
        this.max=max;
        width = (max-min)/buckets+1;
    }

    private int calBucketIndex(int value) {
        return (value-min)/width;
    }

    private int b_r(int i) {
        return min+(i+1)*width-1;
    }
    private int b_l(int i) {
        return min+i*width;
    }

    /**
     * Add a value to the set of values that you are keeping a histogram of.
     * @param v Value to add to the histogram
     */
    public void addValue(int v) {
    	// some code goes here
        ntup++;
        counts[calBucketIndex(v)]++;
    }

    /**
     * Estimate the selectivity of a particular predicate and operand on this table.
     * 
     * For example, if "op" is "GREATER_THAN" and "v" is 5, 
     * return your estimate of the fraction of elements that are greater than 5.
     * 
     * @param op Operator
     * @param v Value
     * @return Predicted selectivity of this particular operator and value
     */
    public double estimateSelectivity(Predicate.Op op, int v) {
        int index = calBucketIndex(v);
        int sum = 0;
    	switch (op) {
            case EQUALS:
                if (v>max||v<min) return 0.0;
                return counts[index]*1.0/width/ntup;
            case GREATER_THAN:
            case GREATER_THAN_OR_EQ:
                if (v>=max) return 0.0;
                else if (v<=min) return 1.0;
                for (int i=index;i< counts.length;i++) {
                    if (i==index) {
                        sum+=counts[index]*(b_r(i)-v+1);
                    }else {
                        sum+=counts[i];
                    }
                }
                return sum*1.0/width/ntup;
            case LESS_THAN:
            case LESS_THAN_OR_EQ:
                if (v>=max) return 1.0;
                else if (v<=min) return 0.0;
                for (int i=0;i<=index;i++) {
                    if (i==index) {
                        sum+=counts[index]*(v+1-b_l(i));
                    }else {
                        sum+=counts[i];
                    }
                }
                return sum*1.0/width/ntup;
            case NOT_EQUALS:
                if (v>max||v<min) return 1.0;
                return 1-counts[index]*1.0/width/ntup;
            default:
                return -1.0;
        }
    }
    
    /**
     * @return
     *     the average selectivity of this histogram.
     *     
     *     This is not an indispensable method to implement the basic
     *     join optimization. It may be needed if you want to
     *     implement a more efficient optimization
     * */
    public double avgSelectivity()
    {
        // some code goes here
        return 1.0;
    }
    
    /**
     * @return A string describing this histogram, for debugging purposes
     */
    public String toString() {
        // some code goes here
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<counts.length;i++) {
            int b_l = i*width;
            int b_r = (i+1)*width-1;
            sb.append(String.format("[%d, %d]:%d\n", b_l,b_r,counts[i]));
        }
        return sb.toString();
    }
}
